﻿#define _CRT_SECURE_NO_WARNINGS
#pragma once
#include <iostream>
#include <vector>
using namespace std;
#include <assert.h>
#include <thread>
#include <mutex>
#include <algorithm>
#include <unordered_map>
#ifdef _WIN32
#include <Windows.h>
#else
// linux下brk mmap等
#endif


// 直接去堆上按⻚申请空间
inline static void* SystemAlloc(size_t kpage)
{
#ifdef _WIN32
	void* ptr = VirtualAlloc(0, kpage * (8 * 1024), MEM_COMMIT | MEM_RESERVE,
		PAGE_READWRITE);
#else
	// linux下brk mmap等
#endif
	if (ptr == nullptr)
		throw std::bad_alloc();
	return ptr;
}


inline static void SystemFree(void* ptr)
{
#ifdef _WIN32
	VirtualFree(ptr, 0, MEM_RELEASE);
#else
	// sbrk unmmap等
#endif
}

static const size_t MAX_BYTES = 256 * 1024;
static const size_t NFREELISTS = 208;
static const size_t NPAGES = 129;
//每页8kb 2^13
static const size_t PAGE_SHIFT = 13;

#ifdef _WIN64
	typedef unsigned long long PAGE_ID;
#elif _WIN32
	typedef size_t PAGE_ID;
#endif




//获得头部的指针
static void*& NextObj(void* obj)
{
	return *(void**)obj;
}
//管理小对象的自由链表
class FreeList
{
public:
	void Push(void* obj)
	{
		assert(obj);
		//头插
		void* tmp = _freelist;
		void* cur = _freelist;
		//int i = 0;
		//while (cur!=nullptr)
		//{
		//	cur = NextObj(cur);
		//	i++;
		//	if (i == _size+1)
		//	{
		//		int x = 0;
		//	}
		//}
		//if (i != _size)
		//{
		//	int x = 0;
		//}

		//*(void**)obj = _freelist;
		NextObj(obj) = _freelist;
		_freelist = obj;
		++_size;

		//cur =_freelist;
		//i = 0;
		//while (cur)
		//{
		//	cur = NextObj(cur);
		//	i++;
		//	if (i == _size+ 1)
		//	{
		//		int x = 0;
		//	}
		//}
		//if (i != _size)
		//{
		//	int x = 0;
		//}
	}
	void PushRange(void* start, void* end,size_t n)
	{

		void* cur = start;
		//int i = 0;
		//while (cur)
		//{
		//	cur = NextObj(cur);
		//	i++;
		//	if (i == n+1)
		//	{
		//		int x = 0;
		//	}
		//}
		//if (i != n)
		//{
		//	int x = 0;
		//}

		NextObj(end) = _freelist;
		_freelist = start;
		_size += n;

		//cur = _freelist;
		//i = 0;
		//while (cur)
		//{
		//	cur = NextObj(cur);
		//	i++;
		//	if (i == _size + 1)
		//	{
		//		int x = 0;
		//	}
		//}
		//if (i != _size)
		//{
		//	int x = 0;
		//}
	}
	void PopRange(void*& start, void*& end, size_t n)
	{
		assert(n <= _size);
		start = _freelist;
		end = start;


		//void* cur = start;
		//int i = 0;
		//while (cur)
		//{
		//	cur = NextObj(cur);
		//	i++;
		//}
		//if (i != n)
		//{
		//	int x = 0;
		//}

		for (size_t i = 0; i < n - 1; i++)
		{
			//错误（原因：end = NextObj(start)）
			end = NextObj(end);
		}

		_freelist = NextObj(end);
		NextObj(end) = nullptr;
		_size -= n;

		//cur = _freelist;
		//i = 0;
		//while (cur)
		//{
		//	cur = NextObj(cur);
		//	i++;
		//	if (i == _size + 1)
		//	{
		//		int x = 0;
		//	}
		//}
		//if (i != _size)
		//{
		//	int x = 0;
		//}
	}

	size_t Size()
	{
		return _size;
	}
	void* Pop()
	{
		//头删
		void* obj = _freelist;
		_freelist = NextObj(obj);
		--_size;

		//void* cur = _freelist;
		//int i = 0;
		//while (cur)
		//{
		//	cur = NextObj(cur);
		//	i++;
		//}
		//if (i != _size)
		//{
		//	int x = 0;
		//}
		return obj;
	}
	bool Empty()
	{
		return _freelist == nullptr;
	}
	size_t& MaxSize()
	{
		return _maxsize;
	}
private:
	void* _freelist = nullptr;
	size_t _maxsize = 1;
	size_t _size = 0;
};


class SizeClass
{
public:
	// 整体控制在最多10%左右的内碎⽚浪费
    // [1,128]              8byte对⻬      freelist[0,16)
    // [128+1,1024]         16byte对⻬     freelist[16,72)
	// [1024+1,8*1024]       128byte对⻬    freelist[72,128)
	// [8*1024+1,64*1024]    1024byte对⻬   freelist[128,184)
	// [64*1024+1,256*1024] 8*1024byte对⻬ freelist[184,208)
	//size_t _RoundUp(size_t size, size_t alignNum)
	//{
	//	size_t alignSize = 0;
	//	if (size % alignNum != 0)
	//	{
	//		alignSize = (size / alignNum + 1) * alignNum;
	//	}
	//	else
	//	{
	//		alignSize = size;
	//	}
	//	return alignSize;
	//}


	//size_t Index(size_t bytes, size_t align)
	//{
	//	if (bytes % align == 0)
	//	{
	//		return bytes / align - 1;
	//	}
	//	else
	//	{
	//		return bytes / align;
	//	}
	//}
	static inline size_t _Index(size_t bytes, size_t align_shift)
	{
		return ((bytes + (1 << align_shift) - 1) >> align_shift) - 1;
	}
	// 计算映射的哪⼀个⾃由链表桶
	static inline size_t Index(size_t bytes)
	{
		assert(bytes <= MAX_BYTES);
		// 每个区间有多少个链
		static int group_array[4] = { 16, 56, 56, 56 };
		if (bytes <= 128) {
			return _Index(bytes, 3);
		}
		else if (bytes <= 1024) {
			return _Index(bytes - 128, 4) + group_array[0];
		}
		else if (bytes <= 81024) {
			return _Index(bytes - 1024, 7) + group_array[1] + group_array[0];
		}
		else if (bytes <= 64 * 1024) {
			return _Index(bytes - 8 * 1024, 10) + group_array[2] +
				group_array[1] + group_array[0];
		}
		else if (bytes <= 256 * 1024) {
			return _Index(bytes - 64 * 1024, 13) + group_array[3] +
				group_array[2] + group_array[1] + group_array[0];
		}
		else {
			assert(false);
		}
		return -1;
	}

	static inline size_t _RoundUp(size_t bytes, size_t align)
	{
		return (((bytes)+align - 1) & ~(align - 1));
	}


	static inline size_t RoundUp(size_t size)
	{
		if (size <= 128)
		{
			return _RoundUp(size, 8);
		}
		else if (size <= 1024)
		{
			return _RoundUp(size, 16);
		}
		else if (size <= 8*1024)
		{
			return _RoundUp(size, 128);
		}
		else if (size<= 64*1024)
		{
			return _RoundUp(size, 1024);
		}
		else if (size<= 256 * 1024)
		{
			return _RoundUp(size, 8*1024);
		}
		else
		{
			//assert(false);
			//return -1;
			return _RoundUp(size, 1 << PAGE_SHIFT);
		}
	}

	// ⼀次从中⼼缓存获取多少个
	static size_t NumMoveSize(size_t size)
	{
		assert(size > 0);
		if (size == 0)
			return 0;
		// [2, 512]，⼀次批量移动多少个对象的(慢启动)上限值
		// ⼩对象⼀次批量上限⾼
		// ⼩对象⼀次批量上限低
		int num = MAX_BYTES / size;
		if (num < 2)
			num = 2;
		if (num > 512)
			num = 512;
		return num;
	}


	// 计算⼀次向系统获取⼏个⻚
 // 单个对象 8byte
 // ...
 // 单个对象 256KB
	static size_t NumMovePage(size_t size)
	{
		size_t num = NumMoveSize(size);
		size_t npage = num * size;
		
		npage >>= PAGE_SHIFT;
		if (npage == 0)
			 npage = 1;
		 return npage;
	}
private:
};

//管理多个连续页
struct Span
{
	//to do
	PAGE_ID _page_id = 0;//起始页号
	size_t _n = 0;    //页的数量
	
	Span* _next = nullptr; //双向链表
	Span* _prev = nullptr;

	size_t _useCount = 0; //
	size_t _objSize = 0;//切好的小对象的大小
	void* _freelist = nullptr;//
	 
	bool _isUse = false;//是否在用
};

class SpanList
{
public:
	SpanList()
	{
		_head = new Span;
		_head->_next = _head;
		_head->_prev = _head;
	}
	bool Empty()
	{
		return _head->_next == _head;
	}
	void PushFront(Span* span)
	{
		Insert(Begin(), span);
	}
	Span* PopFront()
	{
		Span* front = _head->_next;
		Erase(front);
		return front;
	}
	Span* Begin()
	{
		return _head->_next;
	}
	Span* End()
	{
		return _head;

	}
	void Insert(Span* pos, Span* newSpan)
	{
		assert(pos);
		assert(newSpan);

		Span* prev = pos->_prev;

		//错误
		newSpan->_prev = prev;
		newSpan->_next = pos;
		pos->_prev = newSpan;
		prev->_next = newSpan;
	}

	void Erase(Span* pos)
	{
		assert(pos);
		assert(pos != _head);
		pos->_next->_prev = pos->_prev;
		pos->_prev->_next = pos->_next;
	}
public:
	std::mutex _mutex;
private:
	Span* _head;

};
